//#include <iostream>
//#include <unordered_map>
//
//using namespace std;
//
//struct ListNode
//{
//    int key;
//    int value;
//    ListNode* prev;
//    ListNode* next;
//    ListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr){}
//};
//
//class LRUCache 
//{
//private:
//    int capacity;
//    unordered_map<int, ListNode*> cache;
//    ListNode* head;
//    ListNode* end;
//    
//    void removeNode(ListNode* node)
//    {
//        node->prev->next = node->next;
//        node->next->prev = node->prev;
//    }
//
//    void addToHead(ListNode* node)
//    {
//        node->next = head->next;
//        node->prev = head;
//        head->next->prev = node;
//        head->next = node;
//    }
//public:
//    LRUCache(int capacity) : capacity(capacity)
//    {
//        head = new ListNode(0, 0);
//        end = new ListNode(0, 0);
//        head->next = end;
//        end->prev = head;
//    }
//
//    int get(int key) 
//    {
//        if (cache.find(key) != cache.end())
//        {
//            ListNode* node = cache[key];
//            removeNode(node);
//            addToHead(node);
//
//            return node->value;
//        }
//        return -1;
//    }
//
//    void put(int key, int value) 
//    {
//        if (cache.find(key) != cache.end())
//        {
//            ListNode* node = cache[key];
//            node->value = value;
//            removeNode(node);
//            addToHead(node);
//        }
//        else
//        {
//            if (cache.size() == capacity)
//            {
//                ListNode* last = end->prev;
//                removeNode(last);
//                cache.erase(last->key);
//                delete last;
//            }
//            ListNode* newNode = new ListNode(key, value);
//            addToHead(newNode);
//            cache[key] = newNode;
//        }
//    }
//};
//
//int main()
//{
//    LRUCache cache(2);
//
//    cache.put(1, 1);
//    cache.put(2, 2);
//
//    cout << cache.get(1) << endl;
//
//    cache.put(3, 3);
//
//    cout << cache.get(2) << endl;
//
//    cache.put(4,4);
//
//    cout << cache.get(1) << endl;
//    cout << cache.get(3) << endl;
//    cout << cache.get(4) << endl;
//
//    return 0;
//}